class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> count;
        char maxChar;
        int maxCount = 0;
        for (auto ch : s)
        {
            if (maxCount < ++count[ch])
            {
                maxCount = count[ch];
                maxChar = ch;
            }
        }
        int n = s.size();
        string ret;
        ret.resize(n);
        int index = 0;
        if (maxCount > (n + 1) / 2) return "";
        for (int i = 0; i < maxCount; i++)
        {
            ret[index] = maxChar;
            index += 2;
        }
        count.erase(maxChar);
        for (auto [ch, num] : count)
        {
            for (int i = 0; i < num; i++)
            {
                if (index >= n) index = 1;
                ret[index] = ch;
                index += 2;
            }
        }
        return ret;
    }
};